# -*- coding: UTF-8 -*-
import math

def swap_in_array(array, i, j):
    '''
    交换数组array中下标为i和j的2个元素
    '''
    array_len = len(array)
    if i == j or i >= array_len or j >= array_len:
        # 如果i==j则不交换，如果i或者j越界则不交换
        return
    value_first = array[i]
    array[i] = array[j]
    array[j] = value_first
    return array


def sort_bubble(array):
    '''
    冒泡排序 递增
    输入array为数据，在原数组上直接排序
    '''
    array_len = len(array)
    for i in range(0, array_len):
        # 需要处理array_len轮
        for j in range(0, array_len - 1 - i):
            # 每轮把相邻的2个元素中大的那个后置
            if array[j] > array[j+1]:
                swap_in_array(array, j, j+1)
    return array


def sort_select(array):
    '''
    选择排序 递增
    输入array为数据，在原数组上直接排序
    '''
    array_len = len(array)
    for i in range(0, array_len):
        # 需要选择array_len轮，第1轮选择最小的元素，第2轮选择第二小的元素
        min_index = i
        for j in range(i, array_len):
            # 下标i之前的元素已经比下标i及其之后的元素小了，并且下标i之前的元素已经非递减了
            if array[j] < array[min_index]:
                # 从下标i及其之后找到最小的元素，放到位置i上
                min_index = j
        swap_in_array(array, i, min_index)
    return array


def sort_insert(array):
    '''
    直接插入排序 递增
    输入array为数组，在原数组上直接排序
    '''
    array_len = len(array)
    for i in range(1, array_len):
        # 将下标为i的元素插入到下标在[0,i)区间内的子数组内，并且使得插入后[0,i]区间内的子数组仍非递减有序
        insert_index = i
        for j in range(0, i):
            # 在[0,i)区间的子数组中找到合适的插入位置，使得array[i]插入后，[0,i]区间内的子数组仍非递减有序
            if array[i] < array[j]:
                insert_index = j
                break
        # 将下标为i的元素插入到索引insert_index，先在索引i上将其删除，然后直接插入即可
        insert_value = array[i]
        del array[i]
        array.insert(insert_index, insert_value)
    return array


def sort_merge(array):
    '''
    归并排序 递增
    输入array为数组
    '''
    def merge(array_left, array_right):
        '''
        合并2个数组并使得合并结果递增有序
        '''
        # array_left已经非递减有序了
        # array_right已经非递减有序了
        # 将这俩非递减有序的数组合并成1个非递减有序的数组
        result = []
        while array_left and array_right:
            # array_left和array_right都不为空时，把小的先追加到result数组里
            if array_left[0] <= array_right[0]:
                result.append(array_left.pop(0))
            else:
                result.append(array_right.pop(0))
        # 前面操作完之后，array_left或者array_right可能还不空，把不空的直接全部追加到result数组里
        # 此处array_left和array_right只可能有1个不空，且不空的那个数组剩余的所有元素都挺大
        while array_left:
            result.append(array_left.pop(0))
        while array_right:
            result.append(array_right.pop(0))
        return result

    array_len = len(array)
    if array_len < 2:
        return array
    # 找到中间索引，若array长度为偶数则向后取
    index_middle = math.floor(array_len / 2) # floor表示向上取整
    array_left_raw = array[0:index_middle]
    array_right_raw = array[index_middle:]
    array_left_sorted = sort_merge(array_left_raw) # array_left_sorted非递减有序了
    array_right_sorted = sort_merge(array_right_raw) # array_right_sorted非递减有序了
    return merge(array_left_sorted, array_right_sorted) # 合并俩非递减有序的数组


def sort_count(array):
    '''
    计数排序 递增
    输入array为数组
    '''
    array_len = len(array)
    array_value_min = None
    array_value_max = None
    for i in range(0, array_len):
        if None == array_value_min or array_value_min > array[i]:
            array_value_min = array[i]
        if None == array_value_max or array_value_max < array[i]:
            array_value_max = array[i]
    # value_counts的长度是array_value_max - array_value_min + 1
    value_counts = [0] * (array_value_max - array_value_min + 1)
    for i in range(0, array_len):
        array_item_value = array[i]
        array_item_target_index = array_item_value - array_value_min
        value_counts[array_item_target_index] = value_counts[array_item_target_index] + 1
    array_sorted = []
    for i in range(0, len(value_counts)):
        value_count = value_counts[i]
        for j in range(0, value_count):
            array_sorted.append(i + array_value_min)
    return array_sorted


def sort_fast(array):
    '''
    快速排序 填坑法 递增
    输入array为数组，在原数组上直接排序
    '''
    def partition(array, index_start, index_end):
        '''
        定义下标为index_start的元素为基准元素
        将所有小于基准元素的元素放在基准元素左边，将所有大于基准元素的元素放在基准元素右边
        直接在原数组上修改
        函数返回基准元素的下标
        '''
        value_base = array[index_start]
        i = index_start
        j = index_end
        while i < j:
            while i < j and array[j] >= value_base:
                j = j - 1
            array[i] = array[j]
            while i < j and array[i] < value_base:
                i = i + 1
            array[j] = array[i]
        array[i] = value_base
        return i
    
    def quick_sort(array, index_start, index_end):
        '''快排'''
        if index_start >= index_end:
            return
        index_base = partition(array, index_start, index_end)
        quick_sort(array, index_start, index_base - 1)
        quick_sort(array, index_base + 1, index_end)
    
    quick_sort(array, 0, len(array) - 1)
    return array
            

def sort_heap(array):
    '''
    堆排序 递增
    输入array为数组，在原数组上直接排序
    '''
    def adjust_heap_insert(array, index_adjust):
        '''模拟在index_adjust插入新元素（实际上在array中index_adjust处已经有元素了），确保是大顶堆'''
        index_parent = (index_adjust - 1) // 2
        if index_parent < 0:
            return
        if array[index_adjust] > array[index_parent]:
            swap_in_array(array, index_adjust, index_parent)
            adjust_heap_insert(array, index_parent)
    
    len_array = len(array)
    logic_len = len_array
    for j in range(0, len_array):
        for i in range(0, logic_len):
            adjust_heap_insert(array, i)
        swap_in_array(array, 0, logic_len - 1)
        logic_len = logic_len - 1
    return array